The invention relates to a computer graphics animation method as described in the preamble of claim 1.
Such a method is known from a Masters thesis by D. Dekkers, laid open at the Technical University of Eindhoven in February 1997.
Implicit surface definitions form a powerful tool for defining a surface with a variable shape for use in computer graphics. The implicit surface is defined by means of a function whose arguments are coordinates in the space in which the surface lies. The points on the implicit surface are points whose coordinates satisfy an equation involving this function. For example, a spherical surface can be defined by means of a function which is the sum of squares of the coordinates, by requiring that for points on the surface the function should have a predetermined positive value. Other, more complicated surfaces can be defined by combining (e.g. adding) functions in the equation.
Although an implicit surface definition is a powerful tool for defining a surface, such a definition is less convenient for actually rendering the surface, i.e. for computing an image of a scene containing the surface.
Dekkers proposes to compute from the implicit surface definition a mesh of flat triangles and to render that mesh using flat triangles.
This is attractive because available hardware for rendering surfaces is optimized for surfaces that are made up of a mesh of flat triangles. The linear properties of the equations that describe such triangles make it possible to render such triangles at great speed with high efficiency.
Hardware that does not use flat triangles is an unattractive alternative: non-linear surface definitions which require the solution of non-linear equations to find points on the surface cannot be rendered with such great speed. Moreover, most graphics tasks require mostly or only flat triangles so any hardware for rendering implicit surfaces must be provided in addition to available hardware that is optimized for rendering flat triangles.
Implicit surface definitions are very suitable for defining an animated surface with a time-varying shape, for example by using a function which is the sum of two sub-functions and translating or rotating one of the sub-function relative to the other as a function of time.
Preferably, images of such animated surfaces with time varying shape should be computed in real-time, that is, as fast as these images replace one another on a display device. This is convenient for example for computer game applications in which the shape is controlled interactively by a player.
However, computation of a mesh of flat triangles from an implicit surface definition is very time consuming. Generally it is needed to solve the equation containing the function iteratively, because the function is non-linear. In addition, corner points in the mesh have to be distributed over the surface in order to limit the approximation errors introduced by approximating the surface by flat triangles and in order to avoid that too many flat triangles need to be rendered.
Dekker has proposed to reduce the time needed to compute the mesh of flat triangles during animation by using the corner points of the mesh which have been computed for an image at first point in time as a starting point for computing corresponding corner points of the mesh for an image at a second point in time, close to the first point in time. Thus only a few iterations are needed to obtain updated corner points which provide a sufficient approximation of the surface. The distribution of the corner points can also largely be taken over from the first point in time. Dekkers proposes to incorporate in the iterations a shift of the corner points parallel to the surface in order to maintain an optimal distribution.
However, Dekkers""s method is still very time consuming and leaves animation using implicit surface definitions an expensive option for computer graphics.
It is an object of the invention to make it possible to speed up computer animation using implicit surface models.
The method according to the invention is characterized by the characterizing part of claim 1.
According to the invention the implicit surface definition is used to compute control points of a non-linear coordinate valued function which approximates the implicit function. A coordinate valued function is a function which assigns coordinates on a surface to arguments which parametrize a position on a surface. An example of a coordinate valued function is a weighted sum of Bernstein polynomials such as used to define a Bezier shape.
Because a non-linear coordinate valued function is more powerful for describing curved shapes than a flat triangle, much less control points need to be computed for an approximation with a given accuracy than in the case that the implicitly defined surface is approximated by a mesh of flat triangles.
Subsequently, the coordinate valued function is used to compute the corner points in a mesh of flat polygons. This computation can be performed much faster than when the corner points are computed directly from the implicit surface definition. Because the computation of corner points from a coordinate valued function can also be applied to other rendering problems it is economically more attractive to provide dedicated hardware for this computation, making the method even faster.
During animation the control points of the coordinate valued function at a first point in time are used as a starting point for computing the control points of the coordinate valued function at a second point in time. Thus, the time consuming iterations are only performed for the control points and not for all corner points of the mesh of flat polygons. As a result, the computation time needed for iteration is reduced.
In an embodiment of the method according to the invention the non-linear coordinate function corresponds to a mesh of abutting second degree triangles. This is a surface representation that is particularly suitable for conversion to flat triangles.